import { Compare, defaultCompare, DOES_NOT_EXIST, defaultDiff, defaultEquals } from '../../util';
import { quickSort } from '../sorting/quick-sort';

/**
 * 内插搜索：改良版的二分搜索，在步骤1使用一个特殊的公式去选择一个值。
 * 1.在待选区间里利用公式选择一个值，如果选择值就是待搜索值就直接返回；
 * 2.如果待搜索值比选择值要小，就将目前区间的左区间（较小区间）作为待选区间，然后重复步骤1；
 * 3.如果待搜索值比选择值要大，就将目前区间的右区间（较大区间）作为待选区间，然后重复步骤1。
 * @param array 原数组
 * @param value 待搜索值
 * @param compareFn 比较函数
 * @param equalsFn 是否相等
 * @param diffFn 相减
 * 先算出搜索值在“max和min的差值”的占比，再将“max的索引和min的索引的差值”乘以这个“占比”，
 * 就可以大致推出搜索值所在的索引
 */
export function interpolationSearch<T>(
    array: T[],
    value: T,
    compareFn = defaultCompare,
    equalsFn = defaultEquals,
    diffFn = defaultDiff,
): number {
    // 内插搜索的前提条件是该数组已排序（默认升序），我们用快速排序先排一下
    const sortedArray = quickSort(array);
    // 待搜索区的最小值的索引
    let low: number = 0;
    // 待搜索区的最大值的索引
    let high: number = sortedArray.length - 1;

    // low大于high才停止搜索
    while (low <= high) {
        // delta大于二分之一，代表value更靠近high，反之靠近low
        const delta: number = diffFn(value, array[low]) / diffFn(array[high], array[low]);
        // 根据delta的大小预估value的索引
        const position: number = low + Math.floor((high - low) * delta);
        // 待搜索值和中间值相等，找到了，直接返回
        if (equalsFn(value, array[position])) {
            return position;
        }
        // 待搜索值比中间值小，证明待搜索值在左区间，需要将最大值索引替换成mid-1
        else if (compareFn(value, array[position]) === Compare.LESS_THAN) {
            high = position - 1;
        }
        // 待搜索值比中间值大，证明待搜索值在右区间，需要将最小值索引替换成mid+1
        else {
            low = position + 1;
        }
    }
    return DOES_NOT_EXIST;
}
